/*
Dae:20210415 9:37pm
key:1.对于每一个i，只需要考虑它后面的。因此是max(nums[i]+F(nums,i+2),F(nums,i+1));
                                    而不是max nums[i]+F(nums,i+2),nums[i-1]+F(nums,i+1)；i-1没必要考虑
*/
class Solution {
public:
//考虑i与i-1那个带来的金额更大
//尝试自底向上
int F(vector<int>& nums,int i)
{
    if(i>nums.size()-1)
    {
        return 0;
    }
    //if(i==0)
    {
        return max(nums[i]+F(nums,i+2),F(nums,i+1));
    }

    //return nums[i]+F(nums,i+2),nums[i-1]+F(nums,i+1);
}
    int rob(vector<int>& nums) 
    {
        if(nums.size()==0)
        {
            return 0;
        }
        //只有小于3会i不能和i+2相加,直接选最大
        if(nums.size()<=3)
        {
            if(nums.size()==2)
            {
                return 0;
            }
            int j=0;
            for(int i:nums)
            {
                if(i>j)
                {
                    j=i;
                }
            }
            cout<<"1";
            return j;
        }
        //把第一个塞到尾巴
        //nums.push_back(nums[0]);
        return F(nums,0);
    }
};